#计算两个数的最大公因数和最小公倍数


#计算两个数的最大公因数：辗转相除法
def greatestCommonDivisor(a,b):
    if b==0:
        return a
    else:
        greatestCommonDivisor(b,a%b)


#计算两个数最小公倍数:将两个数相乘再除以最大公因数
def leastCommonMultiple(a,b):
    return a*b/greatestCommonDivisor(a,b)

#进一步，我们可以通过扩展欧几里得算法（extend gcd）在求得a和b最大公因数的同时，也得到它们的系数x和y
#从而使ax+by=gcd(a,b)

# 这部分的代码实现请见pdf

